package com.vint.leetcode;

import com.vint.common.ListNode;

/*
 * 1. done
 * 3.
 */
public class Leetcode86 {
    public ListNode partition(ListNode head, int x) {
        if(null==head)return head;
        ListNode root1 = new ListNode(0);
        ListNode tail1 = root1;
        ListNode root2 = new ListNode(0);
        ListNode tail2 = root2;
        while(null!=head){
            if(head.val < x){
            	tail1.next = head;
            	tail1 = tail1.next;
            } else {
	            tail2.next = head;
	            tail2 = tail2.next;
            }
	        head = head.next;
        }
        tail2.next = null;
        tail1.next = root2.next;
        return root1.next;
    }
    public static void main(String[] args) {
    	ListNode r1 = new ListNode(2);
	    r1.next = new ListNode(1);
	    Leetcode86 leetcode86 = new Leetcode86();
	    leetcode86.partition(r1, 2);
	    System.out.println("hello");
    }
}


